package cc.wsyw126.java.nowcoder.sword_offer;

import java.util.ArrayList;

/**
 * Created by Administrator on 2017/4/14.
 * 在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007
 */
public class InversePairs {

    public int InversePairs(int[] array) {
        if (array == null || array.length == 0) return 0;
        return doInversePairs(array, 0, array.length - 1);
    }

    private int doInversePairs(int[] array, int left, int right) {
        if (left >= right) return 0;
        int mid = (left + right) / 2;
        ArrayList<Integer> arrayList = new ArrayList<>();

        int leftCount = doInversePairs(array, left, mid);
        int rightCount = doInversePairs(array, mid + 1, right);
        int leftPosition = left, rightPosition = mid + 1;
        int count = 0;
        while (leftPosition <= mid && rightPosition <= right) {
            if (array[leftPosition] > array[rightPosition]) {
                count+= mid - leftPosition+1;
                if (count >= 1000000007) {
                    count%=1000000007;
                }
                arrayList.add(array[rightPosition]);
                rightPosition++;
            } else {
                arrayList.add(array[leftPosition]);
                leftPosition++;
            }
        }
        if (leftPosition <= mid) {
            for (int i = leftPosition; i <= mid; i++) {
                arrayList.add(array[i]);
            }
        }

        if (rightPosition <= right) {
            for (int i = rightPosition; i <= right; i++) {
                arrayList.add(array[i]);
            }
        }
        for (int i = 0; i < arrayList.size(); i++) {
            array[left + i] = arrayList.get(i);
        }
        return (leftCount%1000000007+ count%1000000007+ rightCount%1000000007)%1000000007;
    }

    public static void main(String[] args) {
        InversePairs inversePairs = new InversePairs();
        int i = inversePairs.InversePairs(new int[]{7, 8, 1, 2});
        System.out.println("i = " + i);
    }
}
